import java.util.*;

class RandomizedQuick
{
 int x[], size;
 public RandomizedQuick(int size)
 {
  Scanner src=new Scanner(System.in);
  this.size=size;
  x=new int[size];
  System.out.println("Enter "+size+" elements");
  for (int i=0; i<size; i++)
    x[i]=src.nextInt();
 }
 private int randomized(int lb, int ub)
 {
  Random obj=new Random();

  int z;
  do
  {
    z=obj.nextInt(ub);
  }
  while(z<lb);
 
   return z;
 }

 public int partition (int lb, int ub)
 {
  int value,down=lb,up=ub,temp,i;
  int ran=randomized(lb,ub);
  System.out.println("\nPivot Randomized Index ="+ran);
  value=x[ran];

  while(true)
  {
   while(x[down]<value)
   down++;
   while (x[up]>value)
    up--;
   if(down<up)
   {
         temp=x[up];
         x[up]=x[down];
         x[down]=temp;
   }
  else break;
  }
  return up;
 }
 public void quickSort (int lb, int ub)
 {
  int p;
  if (lb<ub)
  {
  Scanner src=new Scanner(System.in);
  int a=src.nextInt();
  display();
  System.out.println("LB = "+lb+" UB = "+ub);

        p=partition(lb,ub);
        quickSort(lb,p-1);
        quickSort(p+1,ub);
  }
 }
 public void display()
 {
  System.out.println();

  for (int i=0; i<size; i++)
    System.out.print(x[i]+" ");
  System.out.println();
 }

 public int getSize()
 {
  return size;
 }
}

class RandomizedQuickExp
{
 public static void main(String args[])
 {
  Scanner src=new Scanner(System.in);
  System.out.println("Enter number of elements");
  int n=src.nextInt();
  RandomizedQuick obj=new RandomizedQuick(n);
  System.out.println("The original array");
  obj.display();
  obj.quickSort(0,obj.getSize()-1);
  System.out.println("\nThe Sorted array");
  obj.display();
 }
}


